/*************************************************************************
 * File Name:    Gas_Station.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: 2013-11-1 20:42:07
 *
 * Description:  
 |-----------------------------------------------------------------------
 | Problem: Gas Station
 |
 | There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
 | 
 | You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to
 | its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
 |
 | Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.
 |
 | Note:
 | The solution is guaranteed to be unique.
 |------------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        int N = gas.size();
        vector<int> rem(N);
        
        for (int i = 0; i < N; ++i) {
            rem[i] = gas[i] - cost[i];
        }
        int cnt = 0;
        int left, right;
        
        left = right = 0;
        while (true) {
            if (cnt + rem[right] >= 0) {
                cnt += rem[right];
                right = (right + 1) % N;
            } else {
                left = (left + N - 1) % N;
                cnt += rem[left];
            }
            if (left == right) break;
        }
        if (cnt < 0) return -1;
        return left;
    }
};

int
main(int argc, char *argv[])
{
    Solution sol;
    vector<int> gas, cost;

    gas.push_back(1);
    gas.push_back(2);

    cost.push_back(2);
    cost.push_back(1);

    cout << sol.canCompleteCircuit(gas, cost) << endl;

    return 0;
}
